If you need any help in the design aspects, I'd be happy to help out with input. Are you looking at more free flowing levels, or more of a puzzle element involved? I realize you want this to be hard, so I have a lot of ideas.
Obviously, there should be a few spots where taking damage is required. I'm thinking something like taking damage on a spike bed, then a spindash jump on the spikebed over a gap. Putting in a few platform-falling through objects areas would be cool. Obviously the up-down scroll glitch could be abused in certain areas as well to pass through. There should be some areas that require a huge jump that just barely makes it (obviously, give enough room for error), ala chem plant 2's big shortcut jump at the beginning. If you included tails, a few close call flying areas, like launch base shortcut, would be pretty neat.
I think you should also include some areas where you have to take damage, but you have to keep a ring as well. Say, hitting 3 switches to pass through an area, but every time you hit a switch you take damage, so you must take damage falling to the left in order to keep your one ring. Playing around with underwater timing would also be a good addition, making it very close getting from each air bubble area to the next.
In the autoscroller idea, you should make it so that you have to hit a seemingly impossible to reach checkpoint (i.e. like going below the plane in sky chase, obviously you can come up with another idea here).
Also, you HAVE to have a level where you play around with combos. For example, big jumps down to an item box that propel you, then you have to bounce on a bunch of enemies in a row in order to pass over a gap. Don't make it too ridiculous, and don't make everything too blind, but I think it would be really cool to have to get like a 20 hit combo in order to beat a stage.
Another idea is that maybe you should make people change characters for certain levels? I.e. show mastery of every character in order to pass. Obviously the falling glide can be abused to make it over some ungrabbable wall for knux, and tails could have some perfect flight levels. Sonic could have to use certain shields that are hard to uncover/get to to get past certain parts, and could also do most of the levels.
Manipulating enemies for damage boosts would be pretty cool too.
Sorry my ideas all pretty much come from sonic 2, but I know its quirks better than s3k, and it basically has the same quirks, just multiplied for s3k. I have a ton more ideas that i've thought of, but i'm sure you guys are intelligent and have thought of a lot of the same ones/can work with some of the ideas i gave. Good luck!